package leetcode.recursion;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * leetCode 416
 * Partition to 2 Equal Sum Subsets
 * 划分为2个相等的子集
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * 思路：01背包问题，直接递归
 * 也可以记忆化递归，dp[i][c] 表示使用索引为[0...i]的这些元素,是否可以完全填充一个容量为c的背包

 */
public class Recursion416 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            List<Integer> input = Arrays.stream(str.split(",")).map(i -> { return Integer.parseInt(i); }).collect(Collectors.toList());
            System.out.println(Arrays.toString(input.toArray()));
            Integer [] nums = input.toArray(new Integer[input.size()]);
            new Recursion416().canPartition(nums);
        }
    }

    public boolean canPartition(Integer[] nums) {
        int sum = 0;
        for(int i = 0 ; i< nums.length;i++) sum += nums[i];
        if(sum%2 != 0 || sum <= 0) return false;
        // dp 0表示未访问 ，-1表示不可填满c，1表示可填满
        int [][] dp = new int[nums.length][sum/2 + 1];
        return tryPartition(nums, nums.length - 1, dp, sum/2);
    }

    public boolean tryPartition(Integer[] nums, int index, int [][] dp, int sum){
        if(sum < 0 || index < 0) return false;
        if(sum == 0) return true;
        if(dp[index][sum] != 0){
            return dp[index][sum] == 1;
        }
        boolean flag = tryPartition(nums, index - 1, dp, sum) || tryPartition(nums, index - 1, dp, sum - nums[index]);
        dp[index][sum] = flag? 1 : -1;
        return dp[index][sum] == 1;
    }
}
